package arithmetic.demo12;

import java.util.*;

/**
 * 贪心_贪心+多个交集：用最少数量的箭引爆气球
 */
class Solution {
    public int findMinArrowShots(int[][] points) {
        // 左端点排序
//        以后比较器都用方法
        Arrays.sort(points,(a,b)->{
            return Integer.compare(a[0],b[0]);
        });

        // 初始化
        int ret = 1, left = points[0][0], right = points[0][1];

        // 贪心寻找并集
        for(int i = 1; i < points.length; i++) {
            int leftN = points[i][0], rightN = points[i][1];
            if(right >= leftN) {
                // 更新为最大的右边界
//                左右区间的整合
                right = Math.min(right,rightN);
                left = Math.max(left,leftN);
            } else {
                // 更新结果
                left = leftN;
                right = rightN;
                ret ++;
            }
        }

        return ret;
    }
}


class Test {
    public static void main(String[] args) {
        Integer[] arr = {8,2,4,-1,-9,3,-2147483646,2147483646};
        Arrays.sort(arr,( x, y) ->Integer.compare(x,y));
        for (Integer num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        Solution solution = new Solution();
        System.out.println(solution.findMinArrowShots(new int[][]{{-2147483646, -2147483645}, {2147483646, 2147483647}}));
    }
}



class Solution1 {
    public int integerReplacement(int n) {

        int begin = 1, prev = 1, ret = 0;
        while(begin < n) {
            // 记录上一步
            prev = begin;
            begin *= 2;
            ret++;
        }


        return begin == n ? ret : ret + Math.min(n-prev, begin - n);
    }
}


class Test1 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        System.out.println(solution2.integerReplacement(2147483647));
    }
}

/**
 * dfs_深搜+记忆化搜索：整数替换
 */
class Solution2 {
    public Map<Long,Integer> memo;
    public int integerReplacement(int n) {
        memo = new HashMap<>();
        return  dfs(n);
    }

    public int dfs(long n) {
        // 进行dfs + 记忆化搜索
        // 判断是否深搜过
        if(memo.containsKey(n)) {
            return memo.get(n);
        }

        // 递归出口
        if(n == 1) {
            return 0;
        }

        int ret = 0;
        // 开始深搜
        if(n % 2 == 0) {
            // 偶数时取半
            memo.put(n,dfs(n / 2) + 1);
        } else {
            // 奇数时就分两种情况取最小
            memo.put(n,Math.min(dfs(n-1),dfs(n+1))+1);
        }
        return memo.get(n);

    }
}

/**
 * 贪心_分类讨论+贪心:整数替换
 */
class Solution3 {
    public int integerReplacement(int n1) {
        long n = n1;
        int ret = 0;
        // 分类讨论
        while(n != 1) {
            // 特殊情况判断
            if(n == 3) {
                n--;
                ret++;
                continue;
            }

            // 先分奇偶
            if(n % 2 == 0) {
                n /= 2;
            } else {
                // n > 3 的情况
                if(n % 4 == 3) {
                    n++;
                } else {
                    // n > 1 的情况
                    n--;
                }
            }
            // 统计结果
            ret++;
        }

        return ret;
    }
}

/**
 * 动态规划_dp+排序+最长递增子序列的长度：堆箱子
 */

class Solution4 {
    public int pileBox(int[][] box) {
        // 动态规划思想
        int len = box.length;
        // 创建dp
        int[] dp = new int[len];


        // 排序
        Arrays.sort(box,
                (a,b)->{
                    if(a[0]== b[0]) {
                        return Integer.compare(a[1],b[1]);
                    } else {
                        return Integer.compare(a[0],b[0]);
                    }
                });

        // 初始化
        for(int i = 0; i < len;i++) {
            dp[i] = box[i][2];
        }
        // 填表
        for(int i = 1; i < len; i++) {
            for(int j = 0; j < i; j++) {
                if(box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2]) {
                    dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
                }
            }
        }

        // 统计最后的最大高度
        int ret = 0;
        for(int i = 0; i < len; i++) {
            ret = Math.max(ret,dp[i]);
        }

        return ret;
    }
}


/**
 * 贪心_排序重组+贪心+二分： 俄罗斯套娃信封问题
 */

class Solution5 {
    public int maxEnvelopes(int[][] enve) {
        // 动态规划思想
        int len = enve.length;

        // 先左端点排序后右端点排序
        Arrays.sort(enve,(v1,v2)->{
            if(v1[0]==v2[0]) {
//                如果相同就按照从大到小的顺序排
                return Integer.compare(v2[1],v1[1]);
            } else {
                return Integer.compare(v1[0],v2[0]);
            }
        });

        // 临时存储信封的高度即可
        List<Integer> tmp = new ArrayList<>();
        tmp.add(enve[0][1]);

        // 进行贪心+二分
        for(int i = 1; i < len; i++) {
            int num = enve[i][1] , sz = tmp.size();
            // 如果数据很大
            if(num > tmp.get(sz-1)) {
                tmp.add(num);
            }  else {
                int left = 0 , right = sz - 1;
                // 二分查找到较大值的左边界
                while(left < right) {
                    int mid = left + (right - left) / 2;
                    if (num > tmp.get(mid)) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 修改位置
                tmp.set(left, num);
            }
        }

        return tmp.size();
    }
}


